package com.java.恋上算法.数据结构._03_链表.circle;

import com.java.恋上算法.数据结构._03_链表.AbstractList;

/**
 * @desc: 双向循环链表
 * @author: zhanghongqiang01@baijiahulian.com
 * @date: 2021/8/21/0021 下午 08:55
 */
public class CircleLinkedList<E>  extends AbstractList<E> {

    private Node<E> first ;
    private Node<E> last;

    /**
     * 节点类定义
     * @param <E>
     */
    private static class Node<E>{
        E element;
        Node<E> prev; // 上一个节点
        Node<E> next; // 下一个node的地址
        // 构造函数，接好上一个节点和下一个节点这两根线
        public Node(Node<E>prev,E element,Node<E> next){
            this.prev = prev;
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();

            // prev + index + next
            if (prev != null) {
                sb.append(prev.element);
            } else {
                sb.append("null");
            }

            sb.append("_").append(element).append("_");

            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }

            return sb.toString();
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element =element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        // size == 0
        // index == 0
        if (index == size){ // 往最后面添加元素
            Node<E> oldLast = last;
            last = new Node<>(oldLast,element,first);
            if (oldLast == null){ // 如果是链表添加的第一个元素
                first = last;
                first.next =first;
                first.prev =first;
            }else {
                oldLast.next = last; // .next 考虑问题首先考虑是否为空
                first.prev = last;
            }
        }else { // 往 index == 0 或者 index < size 添加元素;
            // index就是新添加节点的下一个，index节点的上一个，就是新添加节点的上一个
            Node<E> next = node(index);
            Node<E> prev= next.prev;
            // 创建节点已经连上两根线
            Node<E> node = new Node<>(prev,element,next);
            // next节点赋值给 上一个节点的next和下一个节点的prev
            next.prev = node;
            prev.next = node ;

            if (index == 0){ // next == first;
                first = node;
            }
        }

        size ++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = first;
        if (size ==1){
            first = null;
            last = null;
        }else {
            node = node(index);
            Node<E> prev = node.prev;
            Node<E> next = node.next;
            prev.next = next ;
            next.prev = prev;

            // 取出的就是头结点
            if (node == first){ // index == 0
                first = next;
            }
            // 取出的是最后一个节点
            if (node == last){ // index == size -1;
                last = prev;
            }
        }

        size --;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            // 遍历节点
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) {
                    return i;
                }
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) {
                    return i;
                }
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 获取index位置对应的节点对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);

        // 二分查找，< 1/2 的从左往右查， > 1/2 的从右往左查
        if (index < (size >> 1)){
            Node<E> node = first;
            for (int i = 0; i < index; i++){
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size -1; i > index ;i--){
                node = node.prev;
            }
            return node;
        }
    }


    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(node);

            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}
